The present invention relates to the hardware of digital systems, and in particular, it relates to a method and respective hardware logic circuit for implementing partially programmable Finite State Machines.
Developing a complex VLSI-chip is, despite all the verification tools like simulation and formal verification, still an error prone process. Experience shows that usually, there are some errors after the silicon has been built, i.e., the chip is present in hardware form. Typically, those errors are located in the control logic of the chip and not in the data flow logic.
Finite State Machines are the main prior art means to implement the control logic of a digital design. There are numerous tools available, which support the design of such machines. Typically the bugs are associated with the FSMs and it would be highly desirable to make those machines programmable. Full programmability is possible using RAM based techniques; however, the circuit costs are usually prohibitive.
Prior art Finite State Machines (FSM) on the one hand are widely used to implement said control logic. Errors occurring in the state machine cannot be repaired in prior art. After having recognized that an error is present, the chip/circuit logic must be corrected and the hardware must be newly built in silicon.
Another approach to implement the control logic is highly theoretic and not reduced to useful practice until now. This approach would include using fully programmable RAM-based techniques, which generates, however, much too high cost.
Thus, hard-wired technology is preferred to implement said error-prone control logic, and hardware developers suffer from longer development periods required to repeat the “Cementation” of the control logic into silicon “hard wiring”.
The principle of a “hard wired” finite state machine is shown in FIG. 1:                It consists essentially of a state register 10, which holds the current state and two functions of 12, and nf 14 to calculate the outputs and the next state, respectively. The functions “nf” for the next state function and “of” for the current output may be implemented as combinational logic as shown in FIG. 1 or with a RAM as mentioned above.        
The U.S. Pat. No. 5,825,199 discloses the need for providing a reprogrammable state machine. Further, general requirements are set up which should be fulfilled with such reprogrammable state machine, as are:
It should be implemented using a minimal amount of silicon real estate,                the mechanism should have a minimal affect on the timing and performance of the state machine since state machines are very critical in timing, and        the programming mechanism should be flexible in that it should allow for the reprogramming of the behavior of the state machine arbitrarily within the limits of state bits, inputs and outputs, and using a reasonable number of logic terms.        
Further, in said prior art document, it is disclosed that the improved reprogrammable state machine comprises a programmable logic unit in form of a programmable logic array (PLA), which preferably represents a standard sum of products PLA. This is preferred since it represents the best compromise between silicon area and flexibility. Further, the possibility is disclosed, to use a programmable random access memory (RAM) based PLA, which, however, is stated to be time critical in performance.
Further, a vague and insufficiently enabling teaching is given including a ROM, a RAM and a control unit which produce an output, respectively, which is fed at the input of a state machine programmable logic. The control unit is said to be used for loading the RAM unit with the modified values for the state transitions and/or output transitions for each state, which needs to be modified, i.e. corrected due to an error, which has occurred and been detected. This teaching, however, does not represent an enabling disclosure because the state machine reprogrammable logic cannot already include the corrected output signal, as:    a) it is fully unclear, how an error state is detected and controlled,    b) it is not at all disclosed how a corrected output value may appear at the output of the state machine, and    c) the internal details of the reprogrammable logic of the state machine, which are highly relevant in the underlying context, are not at all disclosed.
Thus, although the before-mentioned U.S. patent has disclosed the need for a reprogrammable state machine of the above-mentioned hardwired type, it does not offer a solution to this problem.